package easy;

import java.util.HashMap;
import java.util.Map;

public class Solution_1763 {

    public String longestNiceSubstring(String s) {
        char[] chars = s.toCharArray();
        Map<Integer, Integer> res = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : chars) {
            Integer count = map.getOrDefault(c, 0);
            map.put(c, ++count);
        }
        for (int i = 0; i < chars.length; i++) {
            int j = chars.length - 1;
            boolean flag = false;
            Map<Character, Integer> temp = new HashMap<>(map);
            char c = chars[i];
            for (; j > i; j--) {
                flag = check(temp);
                if (flag) {
                    break;
                }
                Integer count_1 = temp.get(chars[j]);
                temp.put(chars[j], --count_1);
            }
            if (flag) {
                res.put(i, j);
            }
            Integer count = map.get(c);
            map.put(c, --count);
        }
        int a = 0, b = -1;
        for (Integer key : res.keySet()) {
            int sub = res.get(key) - key;
            if (sub > (b - a) || (sub == (b - a) && key < a)) {
                a = key;
                b = res.get(key);
            }
        }
        return new String(chars, a, b - a + 1);
    }

    private boolean check(Map<Character, Integer> map) {
        for (Character c : map.keySet()) {
            if (map.get(c) > 0) {
                if (97 <= c && c <= 122) {
                    if (!map.containsKey((char) (c - 32)) || map.get((char) (c - 32)) <= 0) {
                        return false;
                    }
                } else {
                    if (!map.containsKey((char) (c + 32)) || map.get((char) (c + 32)) <= 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution_1763 model = new Solution_1763();
        System.out.println(model.longestNiceSubstring("YazaAay"));
        System.out.println(model.longestNiceSubstring("Bb"));
        System.out.println(model.longestNiceSubstring("c"));
        System.out.println(model.longestNiceSubstring("dDzeE"));
        System.out.println(model.longestNiceSubstring("VaiOlVBrVyoGqygbrELjHNyRAVmHDhtSsvLMCIeFStnoyTygcrMduvyYfJQ"));
    }
}
